{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8a88e48c",
   "metadata": {},
   "source": [
    "# 长度最小子数组\n",
    "\n",
    "[209. 长度最小的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)\n",
    "\n",
    "给定一个含有 `n` 个正整数的数组和一个正整数 `target` **。**\n",
    "\n",
    "找出该数组中满足其总和大于等于 `target` 的长度最小的 **子数组** `[numsl, numsl+1, ..., numsr-1, numsr]` ，并返回其长度**。**如果不存在符合条件的子数组，返回 `0` 。\n",
    "\n",
    "**示例 1：**\n",
    "\n",
    "```\n",
    "输入：target = 7, nums = [2,3,1,2,4,3]\n",
    "输出：2\n",
    "解释：子数组 [4,3] 是该条件下的长度最小的子数组。\n",
    "```\n",
    "\n",
    "**示例 2：**\n",
    "\n",
    "```\n",
    "输入：target = 4, nums = [1,4,4]\n",
    "输出：1\n",
    "```\n",
    "\n",
    "**示例 3：**\n",
    "\n",
    "```\n",
    "输入：target = 11, nums = [1,1,1,1,1,1,1,1]\n",
    "输出：0\n",
    "```\n",
    "\n",
    "枚举右端点，不断缩小左端点，具体操作为：\n",
    "\n",
    "- 向右移动右端点后，如果发现此时子数组的和比`target`小，说明右端点移动的不够，还需要再次向右移动，所以继续向右移动右端点\n",
    "- 如果移动后发现，子数组的和比`target`大或相等，则从最左端开始缩小左端点，缩小到最小长度为止。、\n",
    "- 每次缩小后，都把目前的长度和最短长度比较并更新。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "afd94408",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sum = 0\n",
    "        left = 0\n",
    "        ans = n + 1\n",
    "        for right, x in enumerate(nums):\n",
    "            sum += x\n",
    "            \n",
    "            ########################### 第一种写法 ###########################\n",
    "            # 缩小之后是否仍然比target大，否则就不用缩小\n",
    "            while sum - nums[left] >= target:\n",
    "                sum -= nums[left]\n",
    "                left += 1\n",
    "            # 缩到最小程度之后验证是否比target大\n",
    "            if sum >= target:\n",
    "                ans = min(ans, right - left + 1)\n",
    "                \n",
    "            ########################### 第二种写法 ###########################\n",
    "            # # 右端点加进来之后立马判断是否比target大，之后再缩小左端点，缩小之后再看是否满足大于target的要求\n",
    "            # while sum >= target:\n",
    "            #     ans = min(ans, right - left + 1)\n",
    "            #     sum -= nums[left]\n",
    "            #     left +=1 \n",
    "\n",
    "        return ans if ans < n + 1 else 0\n",
    "\n",
    "\n",
    "sol = Solution()\n",
    "\n",
    "\n",
    "print(sol.minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))\n",
    "print(sol.minSubArrayLen(15, [1, 2, 3, 4, 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9768ebb4",
   "metadata": {},
   "source": [
    "这个算法的时间复杂度为$O(n)$，为什么呢，因为每次`right`改变的时候，内层循环的`left`不是每次都从0开始向右移动的，而是从算法开始到结束，一次性从0往右移动。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "854c136d",
   "metadata": {},
   "source": [
    "# 无重复字符的最长子串\n",
    "\n",
    "给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长 子串** 的长度。\n",
    "\n",
    "**示例 1:**\n",
    "\n",
    "```\n",
    "输入: s = \"abcabcbb\"\n",
    "输出: 3 \n",
    "解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。\n",
    "```\n",
    "\n",
    "**示例 2:**\n",
    "\n",
    "```\n",
    "输入: s = \"bbbbb\"\n",
    "输出: 1\n",
    "解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。\n",
    "```\n",
    "\n",
    "**示例 3:**\n",
    "\n",
    "```\n",
    "输入: s = \"pwwkew\"\n",
    "输出: 3\n",
    "解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。\n",
    "     请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。\n",
    "```\n",
    "\n",
    "[3. 无重复字符的最长子串 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/)\n",
    "\n",
    "和最短的子数组的思路一样，枚举右端点，移动左端点。\n",
    "\n",
    "最重要的一点是，可能出现重复的元素一定是和新加进来的元素重复。\n",
    "\n",
    "另外，如何判断重复？ 可以使用一个字典，保存每个字符出现的次数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ef12cb84",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "from typing import Counter\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        counter = Counter()\n",
    "        for right, char in enumerate(s):\n",
    "            # 把右端点放到字典里\n",
    "            counter[char] += 1\n",
    "            # 如果该字符出现的次数大于1，则移动左端点\n",
    "            while counter[char] > 1:\n",
    "                counter[s[left]] -= 1\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "sol = Solution()\n",
    "print(sol.lengthOfLongestSubstring(\"abcabcbb\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cc5563b",
   "metadata": {},
   "source": [
    "# 乘积小于 K 的子数组\n",
    "\n",
    "[713. 乘积小于 K 的子数组 - 力扣（LeetCode）](https://leetcode.cn/problems/subarray-product-less-than-k/solutions/1959538/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-jebq/)\n",
    "\n",
    "给你一个正整数数组 `nums` 和一个整数 `k` ，请你返回子数组内所有元素的乘积严格小于 `k` 的连续子数组的数目。\n",
    "\n",
    "**示例 1：**\n",
    "\n",
    "```\n",
    "输入：nums = [10,5,2,6], k = 100\n",
    "输出：8\n",
    "解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。\n",
    "需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。\n",
    "```\n",
    "\n",
    "**示例 2：**\n",
    "\n",
    "```\n",
    "输入：nums = [1,2,3], k = 0\n",
    "输出：0\n",
    "```\n",
    "\n",
    "同样的，右端点遍历，左端点缩小。就是求以某个数为右端点时，乘积小于k的最长子数组。一旦这个最长子数组求出来后，假设是`[l, r]`，其中的从`[l, r], [l+1, r], ..., [r,r]`的所有子数组都一定满足乘积小于k，其数量为：`r - l + 1`。最后把所有右端点的`r-l+1`加起来即为最后的答案。\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "5b93a945",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        left = 0\n",
    "        prod = 1\n",
    "        ans = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            prod *= num\n",
    "            while prod >= k:\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "\n",
    "sol = Solution()\n",
    "print(sol.numSubarrayProductLessThanK([10,5,2,6], 100))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tmp",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
